package hh.leecode;

import java.util.Arrays;

/**
 * 翻转链表，单链表 input 12345,2,4  2-4号元素翻转   output 14325
 */
public class s数据结构_链表_翻转链表2_between {


    public static void main(String[] args) {
        Node head = new Node(null, 1);
        Node current = head;

        for (Integer e : Arrays.asList(2, 3, 4, 5, 6, 7, 8)) {
            current.next = new Node(null, e);
            current = current.next;
        }

        Node reverse = reverseBetweenWithDummy(head, 1, 8);
        while (reverse != null) {
            System.out.println(reverse.val);
            reverse = reverse.next;
        }
    }


    /**
     * 翻转后，必须有一个节点连接翻转后的head，如果start>1还好,我可以找到这样的节点,如果=1,这个节点就是翻转后的首节点
     *
     * 使用一個dummy 节点， 当s=1，
     * @param node
     * @param s
     * @param e
     * @return
     */
    public static Node reverseBetweenWithDummy(Node node, int s, int e) {
        if (node == null) return null;
        if (s <= 0 || e - s < 0) {
            return node;
        }
        Node dummy = new Node(node, -1);
        Node start = dummy;

        for (int i = 1; i < s; i++) {
            start = start.next;
        }


        Node prev = start.next;
        Node current = prev.next;
        Node end = prev;
        for (int i = 0; i < e - s; i++) {
            if (current != null) {
                Node next = current.next;
                current.next=prev;
                prev = current;
                current = next;
            }
        }


        start .next = prev;

        end.next = current;

        return dummy.next;





    }


    /**
     * 12 3456 78
     * <p>
     * 翻转 3-6
     * <p>
     * 截取 3456  记住head=1 start=2 end=3  tail=7
     * <p>
     * 翻转链表使用的是prev 和current滑动窗口.
     * 需要处理 start=1的情况
     */
    public static Node reverseBetween(Node node, int s, int e) {
        if (node == null) return null;
        if (s <= 0 || e - s < 0) {
            return node;
        }
        // 划分区间，记住start 和end

        Node start = node;
        for (int i = 1; i < s - 1; i++) {
            start = start.next;
        }

        Node head = s == 1 ? null : node;


        Node prev = start.next;
        if (head == null) prev = node;
        Node end = prev;
        Node current = prev.next;
        for (int i = 0; i < e - s; i++) {
            if (current != null) {
                Node next = current.next;
                current.next = prev;
                prev = current;
                current = next;
            }
        }

        if (head == null) {
            head = prev;
        } else {
            start.next = prev;
        }

        // 处理tail
        end.next = current;

        return head;

    }


    public static class Node {
        Node next;
        Object val;

        public Node(Node next, Object val) {
            this.next = next;
            this.val = val;
        }

        @Override
        public String toString() {
            return "{" +
                    "val=" + val +
                    '}';
        }

        public Node() {

        }
    }


}






